Field of the Invention
The invention relates to a method and an apparatus for determining a route from a starting point to a destination point, both points being located on a digitized road network.
U.S. Pat. No. 4,984,168 to Neukirchner et al. discloses a process for quickly and reliably determining a route between a starting point and a destination point in a navigation system. This patent is based on the consideration that in the vicinity of the starting point and destination, traffic is carried over secondary roads, while the longer distances are covered over highways and superhighways. In consequence of merely considering roads carrying long-distance traffic in a very large region, the variety of possible roads is reduced thereby reducing the time required for route computation.
A system has become known from European patent application EP 0 726 447 A1 (corr. U.S. Pat. No. 5,712,788) which explores paths from a starting point to a destination using a technique of selecting an intermediate destination and calculating the costs of each of the alternative routes. The route to the intermediate destination is communicated to the user of the system while a remainder route from the intermediate destination to the final destination is determined. However, this is done before the calculation of the entire route is completed, regardless of whether the route to the intermediate destination is part of the optimum route to the final destination. Adding a route from a disadvantageous intermediate destination to the final destination may lead to substantial and otherwise unnecessary detours.